package study;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class MinSwapCouples {

    // 我自己想的办法居然对了，哈哈
    public static int minSwapCouples(int[] row) {
        Map<Integer, Integer> relation = new HashMap<>();
        int count = 0;
        for (int i = 0; i < row.length; i++) {
            relation.put(row[i], i);
        }
        for (int i = 0; i < row.length; i = i + 2) {
            if (row[i] % 2 == 0 && row[i] + 1 == row[i + 1]) {
                continue;
            }
            if (row[i] % 2 == 0 && row[i] + 1 != row[i + 1]) {
                relation.put(row[i + 1], relation.get(row[i] + 1));
                relation.put(row[i] + 1, i + 1);
                row[relation.get(row[i + 1])] = row[i + 1];
                row[i + 1] = row[i] + 1;
                count++;
                continue;
            }
            if (row[i] % 2 != 0 && row[i] - 1 == row[i + 1]) {
                continue;
            }
            if (row[i] % 2 != 0 && row[i] - 1 != row[i + 1]) {
                relation.put(row[i + 1], relation.get(row[i] - 1));
                relation.put(row[i] - 1, i + 1);
                row[relation.get(row[i + 1])] = row[i + 1];
                row[i + 1] = row[i] - 1;
                count++;
            }
        }
        return count;
    }

    // 利用官网示例程序作为对拍
    public static int minSwapsCouples2(int[] row) {
        int n = row.length;
        int tot = n / 2;
        int[] f = new int[tot];
        for (int i = 0; i < tot; i++) {
            f[i] = i;
        }

        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            add(f, l, r);
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < tot; i++) {
            int fx = getf(f, i);
            map.put(fx, map.getOrDefault(fx, 0) + 1);
        }

        int ret = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ret += entry.getValue() - 1;
        }
        return ret;
    }

    public static int getf(int[] f, int x) {
        if (f[x] == x) {
            return x;
        }
        int newf = getf(f, f[x]);
        f[x] = newf;
        return newf;
    }

    public static void add(int[] f, int x, int y) {
        int fx = getf(f, x);
        int fy = getf(f, y);
        f[fx] = fy;
    }


    public static void main(String[] args) {
        int[] arr;
        int[] arr2;
        Random random = new Random();
        Map<Integer, Integer> test = new HashMap<>();
        int n = random.nextInt(30);
        System.out.println(n);
        arr = new int[2 * n];
        arr2 = new int[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            int val = random.nextInt(2 * n);
            while (test.containsKey(val)) {
                val = random.nextInt(2 * n);
            }
            test.put(val, val);
            arr[i] = val;
        }
        for (int i = 0; i < 2 * n; i++) {
            arr2[i] = arr[i];
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("---------");
        int ret1 = minSwapCouples(arr);
        int ret2 = minSwapsCouples2(arr2);
        System.out.println(ret1);
        System.out.println(ret2);
        System.out.println(Arrays.toString(arr));
    }
}

